import offer.TreeNode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @Author: wangliuyang
 * @Date: 2021/8/16 22:53
 * @Description:98. 验证二叉搜索树
 */
public class Solution_98 {
        public boolean isValidBST(TreeNode root) {
            Deque<TreeNode> stack = new LinkedList<TreeNode>();
            double inorder = -Double.MAX_VALUE;

            while (!stack.isEmpty() || root != null) {
                while (root != null) {
                    stack.push(root);
                    root = root.left;
                }
                root = stack.pop();
                // 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
                if (root.val <= inorder) {
                    return false;
                }
                inorder = root.val;
                root = root.right;
            }
            return true;
        }
}
